class Solution {
public:
//跟买卖股票三一摸一样，其中可以优化的点是一共有prices.nums天，那最多就只能进行prices.nums/2比交易，适当优化
    int dp[1010][2][110];
    int maxProfit(int nn, vector<int>& prices) {
        memset(dp, -0x3f, sizeof dp);
        //0:买入1：卖出
        dp[0][1][0] = 0;
        int n = prices.size();
        for(int i = 1; i <= n; ++i)
            for(int k = 0; k <= min(n / 2, nn); ++k)
            {
                int maxv = dp[i - 1][0][k];
                if(k != 0)
                    maxv = max(maxv, dp[i - 1][1][k - 1] - prices[i - 1]);
                dp[i][0][k] = maxv;
                dp[i][1][k] = max(dp[i - 1][0][k] + prices[i - 1], dp[i -1][1][k]);
            }
        int res = 0;
        for(int i = 0; i <= min(n / 2, nn + 1); ++i)
            res = max(res, dp[n][1][i]);
        return res;
    }
};